package com.wtgroup.demo.leetcode.q567_字符串的排列;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/24 17:59
 */
public class Q567_M1 {
    /**
     * 两个字符串字符计数分布一样, 就是排列之一.
     *
     * 效率: 1分;
     * 复杂度: O(n1*n2);
     *
     * 缺陷: i 移动后, 上次的计数信息没有利用起来, 而是应该用滑动窗口方式, 新进来的字符+1, 移除的字符-1.
     */
    public boolean checkInclusion_1(String s1, String s2) {
        int[] s1Counter = new int[26];
        for(int i = 0; i<s1.length(); i++) {
            char c = s1.charAt(i);
            s1Counter[c-'a']++;
        }

        int i=-1,j=0;
        while(++i<s2.length()) {
            int[] s2Counter = new int[26];
            for (j = i; j < i+s1.length() && j<s2.length(); j++) {
                char cur = s2.charAt(j);
                s2Counter[cur-'a'] ++;
                if(s2Counter[cur-'a'] > s1Counter[cur-'a']) {
                    // s1 中没有或s2中更多=>肯定不满足了
                    break;
                }
            }
            boolean flag = true;
            for (int k = 0; k < s2Counter.length; k++) {
                if(s1Counter[k] != s2Counter[k]) {
                    flag = false; // 不满足
                    break;
                }
            }
            if(flag) {
                return true;
            }

            // 跳多了不行, 如 cda dcda
            // i = j+1;
        }


        return false;
    }

    /**
     * 滑动窗口
     * <p>
     * 进和出, 动态计数
     */
    public boolean checkInclusion_2(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }

        int n1 = s1.length();
        int i = n1-1;
        while (++i < s2.length()) {
            char x = s2.charAt(i - n1);
            char y = s2.charAt(i);
            cnt2[x-'a']--;
            cnt2[y-'a']++;
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }

        return false;
    }
}
